package com.jacklei.ch19;

import com.sun.xml.internal.ws.wsdl.writer.document.Part;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import static java.util.Arrays.*;

/*
* 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

 

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
 

提示：

1 <= nums.length <= 200
1 <= nums[i] <= 100

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/partition-equal-subset-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
public class PartitionEqualSubsetSubsetSum {
    public static void main(String[] args) {
        PartitionEqualSubsetSubsetSum p = new PartitionEqualSubsetSubsetSum();
        System.out.println(p.canPartition(new int[]{
                1,1,1,1
                        }));
    }
    public boolean canPartition(int[] nums){
        int length = nums.length;
        if(length == 1) return false;
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if(sum % 2 == 1) return false;
        boolean[][] dp = new boolean[length][sum/2+1];
        for (int i = 0; i < length; i++) {
            dp[i][0] = true;
        }

        for (int i = 1; i < length; i++) {
            for (int j = 0; j < dp[0].length; j++) {

               if(nums[i] <= j){
                   dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i]];
               }else
                   dp[i][j] = dp[i-1][j];
            }
        }
        return dp[length -1][sum/2];
    }
    public boolean canPartition3(int[] nums){
        int length = nums.length;
        if(length == 1) return false;
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if(sum % 2 == 1) return false;
        boolean[] dp = new boolean[sum/2+1];
            dp[0] = true;

        for (int i = 1; i < length; i++) {
            int num = nums[i];
            for (int j = dp.length-1; j >=num; j--) {

                dp[j] = dp[j] || dp[j - num];
            }
        }
        return dp[dp.length-1];
    }
    public boolean canPartition2(int[] nums) {
        int mid = 0;
        for (int num : nums) {
            mid +=num;
        }
        if(mid % 2 == 1) return false;
        Arrays.sort(nums);
        int p =0;
        int a = 0;
        boolean[] flat = new boolean[nums.length];
        if(!sum(nums,mid/2,flat,0))return false;
        int b = 0;
        for (int i = 0; i < flat.length; i++) {
            if(!flat[i]){
                b += nums[i];
            }
        }
        if (b == mid/2) return true;

        return false;

    }
    public boolean sum(int[] nums,int target, boolean[] flat,int p) {
        if(target < 0 || p >= nums.length) return false;
        if(target == 0) return true;

        flat[p]=true;
        int newTarget = target - nums[p];
        boolean sum = sum(nums, newTarget, flat, p+1);
        while (!sum && p < nums.length && p+1 < nums.length) {
            flat[p] = false;
            p++;
            flat[p] = true;
            sum = sum(nums, target - nums[p], flat, p +1);
        }
        if(!sum) flat[p] = false;


        return sum;
    }
    public boolean canPartition1(int[] nums) {
        List<Integer> list = new ArrayList<Integer>(nums.length);
        Arrays.sort(nums);
        for (int num : nums) {
            list.add(num);
        }
        int n = 0;
        Integer dle = 0;
        while ( list.size() > 0 && n < nums.length) {
            int size = list.size();
            Integer integer = list.get(size - 1);
            dle += integer;
            list.remove(dle);
            if (look(list, integer)){
                dle =0;
            }
            n++;
        }
        return list.size() == 0 && dle == 0;

    }
    public boolean look(List<Integer> list, Integer target){
        if (list.contains(target)) {
            list.remove(target);
            return true;
        }
        Integer dle = 0;
        for (int i = 0; i < list.size(); i++) {
            Collections.sort(list);
            Integer integer = list.get(i);
            list.remove(integer);
            dle+= integer;
            Integer temp = target - dle;
            boolean look = look(list, temp);
            if(!look){
                list.remove(integer);
                continue;
            }else {
                return true;
            }
        }
        return false;
    }
}

